Conformant planning is the problem of finding a sequence of actions forachieving a goal in the presence of uncertainty in the initial state or actioneffects. The problem has been approached as a path-finding problem in beliefspace where good belief representations and heuristics are critical for scalingup. In this work, a different formulation is introduced for conformant problemswith deterministic actions where they are automatically converted intoclassical ones and solved by an off-the-shelf classical planner. Thetranslation maps literals L and sets of assumptions t about the initialsituation, into new literals KL/t that represent that L must be true if t isinitially true. We lay out a general translation scheme that is sound andestablish the conditions under which the translation is also complete. We showthat the complexity of the complete translation is exponential in a parameterof the problem called the conformant width, which for most benchmarks isbounded. The planner based on this translation exhibits good performance incomparison with existing planners, and is the basis for T0, the best performingplanner in the Conformant Track of the 2006 International Planning Competition.
展开▼
